FIG. 1 depicts conventional networks 10 and 20 which may be connected to the Internet 30. Each network 10 and 20 includes host 12, 14 and 16 and 22 and 24, respectively. Each network 10 and 20 also includes a switch 18 and 26, respectively, and may include one or more servers such as the servers 17, 19 and 28, respectively. In addition, each network 10 and 20 may include one or more gateways 13 and 25, respectively, to the Internet 30. Not explicitly shown are routers and other portions of the networks 10 and 20 which may also control traffic through the networks 10 and 20 and which will be considered to be inherently depicted by the switches 18 and 26, respectively, and the networks 10 and 20 in general.
FIG. 2 depicts a portion of a typical switch 50, which may be used for the switches 18 and 26 and/or a router (not shown). The switch 50 includes a network processor 52 and storage 54. The switch 50 typically also includes other components (not shown). The network processor 52 manages functions of the switch, including the classification of packets using the rules described below. The storage 54 retains data relating to the rules.
Referring to FIGS. 1 and 2, in order to manage communications in a network, such as the network 10 or 20, filter rules are used. Filter rules are typically employed by switches, routers and other portions of the network to perform packet classification. Each filter rule is used to classify packets which are being transmitted via a network in order to determine how the packet should be treated and what services should be performed. For example, a filter rule may be used in testing packets entering the network from an outside source to ensure that attempts to break into the network can be thwarted. For example, traffic from the Internet 30 entering the network 10 may be tested in order to ensure that packets from unauthorized sources are denied entrance. Similarly, packets from one portion of a network may be prevented from accessing another portion of the network. For example, a packet from some of the hosts 12, 14 or 16 may be prevented access to either the server 17 or the server 19. The fact that the host attempted to contact the server may also be recorded so that appropriate action can be taken by the owner of the network. Such filter rules may also be used to transmit traffic based on the priorities of packets. For example, packets from a particular host, such as the host 12, may be transmitted because the packets have higher priority even when packets from the hosts 14 or 16 may be dropped. The filter rules may also be used to ensure that new sessions are not permitted to be started when congestion is high even though traffic from established sessions is transmitted. Other functions could be achieved based on the filter rule.
Filter rules also typically have a priority. The filter rules can also interact based on the priority for each of the filter rules. The priority of filter rules can be used to determine the action taken when a key matches the ranges for two or more filter rules. In such a case, the filter rule having a higher priority controls the action taken. For example, a first rule may be a default rule, which treats most cases. A second rule can be an exception the first rule. The second rule would typically have a higher priority than the first rule to ensure that where a packet matches both the first and the second rule, the second rule will control. In a conventional system, all of the filter rules are placed in a list based upon their priority. Also in a conventional system, each filter rule has a different priority reflected in their position in the list. Thus, in a conventional system the number of priorities is the same as the number of filter rules. Thus, in a conventional system, the number of priorities of filter rules is large
In order to determine whether a particular rule will operate on a particular packet, a key is tested. The key that is typically used consists of selected fileds, known collectively as the TCP/IP 5-tuple or just the 5-tuple, extracted from the Internet Protocol (IP) and TCP headers of the packet. The IP and TCP headers typically contains five fields of interest: the source address, the destination address, the source port, the destination port and the protocol. These fields are typically thirty-two bits, thirty-two bits, sixteen bits, sixteen bits and eight bits, respectively. Rules typically operate on one or more of these fields. For example, based on the source and/or destination addresses, the rule may determine whether a packet from a particular host is allowed to reach a particular destination address.
Furthermore, the key often contains additional bits other than the fields of the TCP/IP 5-tuple. For example, a TCP SYN (start of session) packet, which starts a session, may be characterized differently than a TCP packet for an existing session. This characterization is accomplished using bits in addition to those in the IP and TCP headers. The additional bits may be used by a filter rule which manages traffic through a network. For example, when the network is congested, the filter rule may proactively drop the TCP SYN packet while transmitting TCP packets for existing sessions. These operations allow the network to continue to operate and help reduce congestion. In order to perform this function, however, the rule utilizes a SYN packet or the additional bits which characterize a packet as a start packet or a packet from an existing session. Thus, the filter rules typically operate using a key that includes at least some fields of the IP header of a packet and may include additional bits.
In testing a key, it is determined whether to enforce a filter rule against a particular packet and thus classify the packet. The key is tested by determining whether certain fields for the key of the packet exactly match range(s) of the rule. Each rule contains a range of values in one or more dimensions. Each dimension corresponds to a field of the key (typically the IP header). One type of filter rule has a range consisting of a single value. In such a case, the key would have to exactly match the value for the rule to operate on the packet. Other rules have ranges which can be expressed using a single prefix. The prefix is a binary number containing a number of ones and zeroes (1 or 0) followed by place holders, or wildcards (*). The lower bound of the range is obtained by replacing all of the wildcards by zeros. The upper bound of the range is determined by replacing all of the wildcards by a one). Other rules have arbitrary ranges. Arbitrary ranges are ranges that cannot be expressed using a single prefix. However, an arbitrary range can be expressed using multiple prefixes.
The switch 50 uses the storage 54 to store data relating to the filter rules. In particular, the storage 54 can store the prefixes and exact values that are used to describe the ranges of the filter rules. Typically, the storage 50 is a memory such as a RAM. The storage 50 would then occupy relatively little space. However, when the prefixes residing in the storage 50 are searched to determine whether a key matches the prefix, the entries in the storage 50 are searched serially. However, the storage 50 could also use a ternary content addressable memory (TCAM). TCAMs include logic, such as a comparator, for each location. The logic allows the entries of the TCAM to be searched in parallel. A TCAM can also store one of three items in a particular location. The TCAM can store a one, a zero, or a place holder in each location. Alternatively, the TCAM can be viewed as storing a mask that indicates where a one or zero can be stored and the ones and zeroes for these locations. The TCAM can thus store the prefixes for the filter rules and rapidly search the contents of the memory.
Although the TCAM could be used for storing prefixes for filter rules, one of ordinary skill in the art will readily recognize that the TCAM is expensive. Because comparators are provided in each location, the TCAM requires a relatively large amount of space. However, it would be desirable for the storage 54 to occupy a small amount of space. In addition, the TCAM also consumes a relatively large amount of power during operation, which is undesirable.
Accordingly, what is needed is a system and method for improving the storage of prefixes for classification rules, preferably filter rules and more efficiently searching the prefixes for a match to the key. The present invention addresses such a need.